package com.kehao.leetcode.middle.dp;

import org.junit.Test;

public class LengthOfLISSolution {

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j]<nums[i]){
                    dp[i] = dp[i]>dp[j]+1?dp[i]:dp[j]+1;
                }
            }
        }
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result>dp[i]?result:dp[i];
        }
        return result;
    }


    @Test
    public void test01(){
        int[] nums = {10,9,2,5,3,7,101,18};
        System.out.println(lengthOfLIS(nums));
    }

    @Test
    public void test02(){
        int[] nums = {0,1,0,3,2,3};
        System.out.println(lengthOfLIS(nums));
    }

    @Test
    public void test03(){
        int[] nums = {7,7,7,7,7,7,7};
        System.out.println(lengthOfLIS(nums));
    }
}
